package com.leetcode;

/**
 * 780. 到达终点
 *
 * @author fy
 * @date 2022/4/9 10:15
 */
public class Solution780 {

    public boolean reachingPoints2(int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) {
            return true;
        }
        if (sx > tx || sy > ty) {
            return false;
        }
        if (sx == tx) {
            return (ty - sy) % tx == 0;
        }
        if (sy == ty) {
            return (tx - sx) % ty == 0;
        }
        return tx >= ty ? reachingPoints(sx, sy, tx % ty, ty) : reachingPoints(sx, sy, tx, ty % tx);
    }

    /**
     * 反向计算
     *
     * @param sx
     * @param sy
     * @param tx
     * @param ty
     * @return
     */
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }

    /**
     * 暴力递归法, 堆栈溢出
     *
     * @param sx
     * @param sy
     * @param tx
     * @param ty
     * @return
     */
    public boolean reachingPoints1(int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) {
            return true;
        }
        if (sx <= tx && sy <= ty) {
            return reachingPoints1(sx, sx + sy, tx, ty) || reachingPoints1(sx + sy, sy, tx, ty);
        }
        return false;
    }

    public static void main(String[] args) {
        int sx = 35;
        int sy = 13;
        int tx = 455955547;
        int ty = 420098884;

        boolean res = new Solution780().reachingPoints(sx, sy, tx, ty);
        System.out.println(res);
    }

}
